#define R return
#define S(z) scanf("%d",&z)
typedef int I;
I m[100][100], r;
I d(I i, I j) {
	I a, b;
	if (i == r)
		R 0;
	a = d(i + 1, j + 1);
	b = d(i + 1, j);
	R m[i][j] + (a > b ? a : b);
}
I main() {
	I i, j, t;
	s(t);
	for (; t--;) {
		s(r);
		for (i = 0; i < r; i++)
			for (j = 0; j < i + 1; j++)
				s(m[i][j]);
		printf("%d\n", d(0, 0));
	}R 0;
}
